{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K-th Smallest in Lexicographical Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findKthNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字典序的第K小数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定整数&nbsp;<code>n</code>&nbsp;和&nbsp;<code>k</code>，返回&nbsp;&nbsp;<code>[1, n]</code>&nbsp;中字典序第&nbsp;<code>k</code>&nbsp;小的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>n = 13, k = 2\n",
    "<strong>输出: </strong>10\n",
    "<strong>解释: </strong>字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 1, k = 1\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-th-smallest-in-lexicographical-order](https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-th-smallest-in-lexicographical-order](https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['13\\n2', '1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n, k) -> int:\n",
    "        cur = 1\n",
    "        prefix = 1\n",
    "\n",
    "        while cur <k:\n",
    "            cnt = self.get_count(prefix,n)\n",
    "            if cur + cnt >k:\n",
    "                prefix *= 10\n",
    "                cur += 1\n",
    "            else:\n",
    "                prefix += 1\n",
    "                cur += cnt\n",
    "        return prefix\n",
    "\n",
    "    def get_count(self, i, n):\n",
    "\n",
    "        if i <= n:\n",
    "            cnt = 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "        a = i\n",
    "        b = i + 1\n",
    "\n",
    "        while True:\n",
    "            a = a * 10\n",
    "            b = b * 10\n",
    "            if n >= b:\n",
    "                cnt += b - a\n",
    "            elif n >= a:\n",
    "                cnt += n - a + 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        # 初始化当前数字为1，k减1（因为我们从1开始计数）\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        # 循环直到k为0\n",
    "        while k > 0:\n",
    "            # 初始化计数器和区间\n",
    "            count = 0\n",
    "            interval = [cur, cur + 1]\n",
    "            # 计算当前数字cur的子节点数量（即在字典序中，以cur为前缀的数字的数量）\n",
    "            while interval[0] <= n:\n",
    "                count += min(n + 1, interval[1]) - interval[0]\n",
    "                interval = [10 * interval[0], 10 * interval[1]]\n",
    "            # 如果k大于等于子节点数量，说明第k小的数字不在以cur为前缀的数字中，将cur加1，k减去子节点数量\n",
    "            if k >= count:\n",
    "                cur += 1\n",
    "                k -= count\n",
    "            # 如果k小于子节点数量，说明第k小的数字在以cur为前缀的数字中，将cur乘以10（即进入下一层），k减1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        # 当k减到0时，循环结束，此时的cur就是第k小的数字\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        cur = 1\n",
    "        while k > 0:\n",
    "            step,first,last = 0,cur,cur+1\n",
    "            while first <= n:\n",
    "                step += min(n+1,last) - first\n",
    "                first *= 10\n",
    "                last *= 10\n",
    "            if step <= k:\n",
    "                cur += 1\n",
    "                k -= step\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        \n",
    "        # 在n的限制下，当前前缀为l的10叉树节点个数；例如n=13, 节点为1前缀树节点为【1, 10, 11, 12, 13】5个\n",
    "        def dfs(l, r):\n",
    "            if l > n: return 0\n",
    "            return min(r, n) - l + 1 + dfs(l * 10, r * 10 + 9)\n",
    "        \n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        # 只有两个操作【平移/向下】\n",
    "        while k:\n",
    "            # 以cur为根的树节点数\n",
    "            steps = dfs(cur, cur)\n",
    "\n",
    "            # k可以囊括以cur为根的节点数，说明不在这颗树中，平移\n",
    "            if k >= steps:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            # 如果k < cur为根的节点数，说明在这颗树中，cur * 10, k-1跳过当前cur节点，向下递归\n",
    "            else:\n",
    "                k -= 1\n",
    "                cur *= 10\n",
    "        return cur\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(x, limit):\n",
    "            a, b = str(x), str(limit)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum(10 ** i for i in range(k)) if k else 0\n",
    "            ans += 10 ** k if (u := int(b[:len(a)])) > x else limit - x * 10 ** k + 1 if u == x else 0\n",
    "            return ans\n",
    "\n",
    "        ans = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(ans, n)\n",
    "            ans = ans + 1 if cnt < k else ans * 10\n",
    "            k -= cnt if cnt < k else 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        res = 1\n",
    "        while k > 0:\n",
    "            cnt = 0\n",
    "            interval = [res, res + 1]\n",
    "            while n >= interval[0]:\n",
    "                cnt += (min(n + 1, interval[1]) - interval[0])\n",
    "                interval[0] *= 10\n",
    "                interval[1] *= 10\n",
    "            if k >= cnt:\n",
    "                k -= cnt\n",
    "                res += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                res *= 10\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_steps(cur):\n",
    "            steps, first, last = 0, cur, cur\n",
    "            while first <= n:\n",
    "                steps += min(last, n) - first + 1\n",
    "                first *= 10\n",
    "                last = last * 10 + 9\n",
    "            return steps\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = get_steps(cur)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = cur * 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def getSteps(cur):\n",
    "            steps, first, last = 0, cur, cur\n",
    "            while first <= n:\n",
    "                steps += min(last, n) - first + 1\n",
    "                first *= 10\n",
    "                last = last * 10 + 9\n",
    "            return steps\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = getSteps(cur)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def childCount(parrent):\n",
    "            res = 0\n",
    "            cur = parrent\n",
    "            nxt = parrent + 1\n",
    "            while True:\n",
    "                cur *= 10\n",
    "                nxt *= 10\n",
    "                if cur > n:\n",
    "                    break\n",
    "                else:\n",
    "                    res += min(n+1, nxt) - cur\n",
    "            return res\n",
    "        \n",
    "        num = 1\n",
    "        rank = 1\n",
    "        while rank != k:\n",
    "            count = childCount(num)\n",
    "            if rank + count < k:\n",
    "                num += 1\n",
    "                rank += count + 1\n",
    "            else:\n",
    "                num *= 10\n",
    "                rank += 1\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getsteps(self, cur, n):\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        cur = 1\n",
    "        while k:\n",
    "            steps = self.getsteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                cur *= 10\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        res = 1\n",
    "        while k > 0:\n",
    "            count = 0\n",
    "            interval = [res, res+1]\n",
    "            while n >= interval[0]:\n",
    "                count += (min(interval[1], n+1) - interval[0])\n",
    "                interval[0] *= 10\n",
    "                interval[1] *= 10\n",
    "            if k >= count:\n",
    "                res += 1\n",
    "                k -= count\n",
    "            else:\n",
    "                res *= 10\n",
    "                k -= 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k-=1\n",
    "        cur = 1\n",
    "        while(k>0):\n",
    "            left,right = cur,cur+1\n",
    "            node_num = 0\n",
    "            while(left<=n):\n",
    "                node_num+=(min(right,n+1)-left)\n",
    "                left*=10\n",
    "                right*=10\n",
    "            if(node_num<=k):\n",
    "                k-=node_num\n",
    "                cur+=1\n",
    "            else:\n",
    "                k-=1\n",
    "                cur*=10\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        #https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1360804/by-jam007-56ee/\n",
    "        k -= 1\n",
    "        cur = 1\n",
    "        while k > 0:\n",
    "            step,first,last = 0,cur,cur+1\n",
    "            while first <= n:\n",
    "                step += min(n+1,last) - first\n",
    "                first *= 10\n",
    "                last *= 10\n",
    "            if step <= k:\n",
    "                cur += 1\n",
    "                k -= step\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findKthNumber(self, n: int, k: int) -> int:\n",
    "#         def getCnt(prefix, n):\n",
    "#             cnt, cur, next = 0, prefix, prefix + 1\n",
    "#             while cur <= n:\n",
    "#                 cnt += min(next, n + 1) - cur\n",
    "#                 cur, next = cur * 10, next * 10\n",
    "#             return cnt\n",
    "        \n",
    "#         poi, prefix = 1, 1\n",
    "#         while poi < k:\n",
    "#             cnt = getCnt(prefix, n)\n",
    "#             if poi + cnt > k:\n",
    "#                 prefix *= 10\n",
    "#                 poi += 1\n",
    "#             else:\n",
    "#                 prefix += 1\n",
    "#                 poi += cnt\n",
    "#         return prefix\n",
    "\n",
    "# class Solution:\n",
    "# \tdef findKthNumber(self, n: int, k: int) -> int:\n",
    "# \t\tres = []\n",
    "# \t\tfor i in range(1, n + 1):\n",
    "# \t\t\tres.append(str(i))\n",
    "# \t\tres.sort()\n",
    "# \t\treturn int(res[k - 1])\n",
    "\n",
    "# res = Solution().findKthNumber(13, 2)\n",
    "# print(res)\n",
    "\n",
    "# 构建字典树的过程需要遍历树的每个节点，最坏情况下是遍历完所有的数字，所以时间复杂度为 O(n)。\n",
    "# 在每个节点的遍历过程中，需要计算子节点数，这也需要 O(n) 的时间。\n",
    "# 综合考虑，总体时间复杂度为 O(n)。\n",
    "\n",
    "# 代码中只使用了常数级别的额外空间，所以空间复杂度为 O(1)。\n",
    "# 这个算法通过构建字典树的方式，巧妙地遍历了字典序中的数字，以找到第k个最小的数字。\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1  # 从数字1开始\n",
    "        k -= 1  # 减去第一个节点1\n",
    "        while k > 0:\n",
    "            steps = 0\n",
    "            interval = [cur, cur + 1]  # 当前节点到下一个节点的范围\n",
    "            while interval[0] <= n:  # 在当前范围内\n",
    "                step = min(n + 1, interval[1]) - interval[0]  # 计算子节点数\n",
    "                interval = [interval[0] * 10, interval[1] * 10]  # 移动到下一层\n",
    "            if k >= steps:  # 如果k大于等于当前子树节点数\n",
    "                cur += 1  # 移动到下一个子节点\n",
    "                k -= steps\n",
    "            else:  # 否则，k小于当前子树节点数\n",
    "                cur *= 10  # 移动到下一层的第一个节点\n",
    "                k -= 1  # 减去根节点\n",
    "        return cur\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "\n",
    "        def findGap(a, b, n):\n",
    "            gap = 0\n",
    "            while a <= n:\n",
    "                gap += min(n + 1, b) - a\n",
    "                a *= 10\n",
    "                b *= 10\n",
    "            return gap\n",
    "\n",
    "        cur = 1\n",
    "        while k > 1:\n",
    "            gap = findGap(cur, cur+1, n)\n",
    "            if gap <= k - 1:\n",
    "                k -= gap\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getsteps(self, cur, n):\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        cur = 1\n",
    "        while k:\n",
    "            steps = self.getsteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                cur *= 10\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k > 0:\n",
    "            left = cur\n",
    "            right = cur + 1\n",
    "            node_num = 0\n",
    "            while left <= n:\n",
    "                node_num += min(right, (n+1)) - left\n",
    "                left = left * 10\n",
    "                right = right * 10\n",
    "            # print(cur, node_num)\n",
    "            node_num -= 1\n",
    "            if node_num < k:\n",
    "                k = k - node_num - 1\n",
    "                cur = cur + 1\n",
    "            else:\n",
    "                cur = cur * 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        node = 1\n",
    "        k -= 1\n",
    "        def getChildNum(n, curNode):\n",
    "            num = 0\n",
    "            left = curNode\n",
    "            right = curNode + 1\n",
    "            while left <= n:\n",
    "                num += min(n+1, right) - left\n",
    "                left = left * 10\n",
    "                right = right * 10\n",
    "            return num\n",
    "\n",
    "        while k > 0:\n",
    "            #计算子节点数量\n",
    "            childNum = getChildNum(n, node)\n",
    "            if childNum > k: # 在子节点中\n",
    "                k -= 1 # 减去当前节点\n",
    "                node *= 10 # 下一节点搜索\n",
    "            else:\n",
    "                k -= childNum\n",
    "                node += 1 # 往右边搜索\n",
    "\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(x, limit):\n",
    "            a, b = str(x), str(limit)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum(10 ** i for i in range(k)) if k else 0\n",
    "            ans += 10 ** k if (u := int(b[:len(a)])) > x else limit - x * 10 ** k + 1 if u == x else 0\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(pref, n)\n",
    "            if cnt < k: pref, k = pref + 1, k - cnt\n",
    "            else: pref, k = pref * 10, k - 1\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def count_num_tree(cur, n):  #计算当前节点cur对应10叉树的结点总数\n",
    "            count, first, last = 0, cur, cur\n",
    "            while first <= n:  #逐层遍历\n",
    "                count += (min(last, n) - first + 1)\n",
    "                first = 10*first\n",
    "                last = last * 10 + 9\n",
    "            return count\n",
    "\n",
    "\n",
    "        cur = 1  # 当前节点\n",
    "        k -= 1  # 遍历当前节点\n",
    "        while k:\n",
    "            count = count_num_tree(cur, n)  # 获取当前节点所在树的节点数量\n",
    "            if count <= k:  # 如果节点数小于k，则遍历右边的树\n",
    "                cur += 1\n",
    "                k -= count\n",
    "            else:           # 否则对子树遍历\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n",
    "\n",
    "#https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1363067/zhi-xing-yong-shi-cong-5-by-kind-curiehx-fdio/\n",
    "\n",
    "#与 第386题 配合理解 效果更佳"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_steps(cur, n):\n",
    "            first, last, steps = cur, cur, 0\n",
    "            while first <= n:\n",
    "                steps += min(last, n)-first + 1\n",
    "                first *= 10 \n",
    "                last = last * 10 + 9\n",
    "            return steps\n",
    "        \n",
    "        cur, k = 1, k-1\n",
    "        while k:\n",
    "            steps = get_steps(cur, n)\n",
    "            if steps<=k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(m, limit):\n",
    "            a, b = str(m), str(limit)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum([10**i for i in range(k)]) if k else 0\n",
    "\n",
    "            u = int(b[:len(a)])\n",
    "            if u > m: ans += 10**k \n",
    "            elif u == m: ans += limit - m * 10**k + 1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(pref, n)\n",
    "            if cnt >= k: pref, k = pref * 10, k - 1\n",
    "            else: pref, k = pref + 1, k - cnt\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(x, limit):\n",
    "            a, b = str(x), str(limit)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum(10 ** i for i in range(k)) if k else 0\n",
    "            ans += 10 ** k if (u := int(b[:len(a)])) > x else limit - x * 10 ** k + 1 if u == x else 0\n",
    "            return ans\n",
    "        \n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(pref, n)\n",
    "            if cnt < k: pref, k = pref + 1, k - cnt\n",
    "            else: pref, k = pref * 10, k - 1\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        r,k=1,k-1\n",
    "        while k:\n",
    "            s,r0,r1=0,r,r\n",
    "            while r0<=n:\n",
    "                s+=min(r1,n)-r0+1\n",
    "                r0,r1=r0*10,r1*10+9\n",
    "            if s<=k:r,k=r+1,k-s\n",
    "            else:r,k=r*10,k-1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def step(self, cur, n):\n",
    "        cnt = 0\n",
    "        first, last = cur, cur\n",
    "        while first <= n:\n",
    "            cnt += min(last,n) - first + 1\n",
    "            first *= 10\n",
    "            last = last*10 + 9\n",
    "\n",
    "        return cnt\n",
    "\n",
    "\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        if len(str(n)) == 1:\n",
    "            return k\n",
    "        res = 1\n",
    "        k -= 1\n",
    "        while k > 0:\n",
    "            nums = self.step(res, n)\n",
    "            if nums <= k:\n",
    "                res += 1\n",
    "                k -= nums\n",
    "            else:\n",
    "                res *= 10\n",
    "                k -= 1\n",
    "        \n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        n = str(n)\n",
    "        def foo(s, n):\n",
    "            if s.startswith('0'): return 0\n",
    "            if s + ':' < n:\n",
    "                return int('1' * (len(n) - len(s) + 1))\n",
    "            if int(s) > int(n):\n",
    "                return 0\n",
    "            if s >= n:\n",
    "                if len(s) == len(n):\n",
    "                    return 1\n",
    "                if len(s) > len(n):\n",
    "                    return 0\n",
    "                return foo(s, s.ljust(len(n) - 1, '9'))\n",
    "            return sum(foo(s + c, n) for c in '0123456789') + 1\n",
    "        ans = ''\n",
    "        k += 1\n",
    "        def dfs(pre):\n",
    "            nonlocal k\n",
    "            k -= 1\n",
    "            if k < 0:\n",
    "                return\n",
    "            if k == 0:\n",
    "                nonlocal ans\n",
    "                ans = pre\n",
    "                return\n",
    "            for c in '0123456789':\n",
    "                child = foo(pre + c, n)\n",
    "                if k > child:\n",
    "                    k -= child\n",
    "                elif int(pre + c) <= int(n):\n",
    "                    dfs(pre + c)\n",
    "        dfs('')\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(p, mx):\n",
    "            a, b = str(p), str(mx)\n",
    "            d = len(b) - len(a)\n",
    "            ans = sum([10**i for i in range(d)]) if d else 0\n",
    "            u = int(b[:len(a)])\n",
    "            if u > p: ans += 10**d\n",
    "            elif u == p: ans += mx - u*10**d + 1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(pref, n)\n",
    "            if cnt < k: pref, k = pref + 1, k - cnt\n",
    "            else: pref, k = pref * 10, k - 1\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def pre_num(pre, limit):\n",
    "            a, b = str(pre), str(limit)\n",
    "            pre_n = len(a)\n",
    "            k = len(b) - pre_n\n",
    "            ans = sum(10 ** i for i in range(k)) if k else 0\n",
    "            u = int(b[:pre_n])\n",
    "            if u > pre:\n",
    "                ans += 10 ** k\n",
    "            elif u == pre:\n",
    "                ans += limit - pre * 10 ** k + 1\n",
    "            return ans \n",
    "        ans = 1\n",
    "        while k > 1:\n",
    "            nums = pre_num(ans, n)\n",
    "            if k > nums:\n",
    "                k -= nums\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans *= 10\n",
    "                k -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur=1\n",
    "        k-=1\n",
    "        while k:\n",
    "            steps=self.getsteps(cur,n)\n",
    "            if steps<=k:\n",
    "                k-=steps\n",
    "                cur+=1\n",
    "            else:\n",
    "                cur*=10\n",
    "                k-=1\n",
    "        return cur\n",
    "\n",
    "\n",
    "    \n",
    "    def getsteps(self,cur,n):\n",
    "        steps,first,last=0,cur,cur\n",
    "        while first<=n:\n",
    "            steps+=min(last,n)-first+1\n",
    "            first*=10\n",
    "            last=last*10+9\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_steps(self, cur, n):\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <=n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last*10 + 9\n",
    "        return steps\n",
    "        \n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.get_steps(cur, n)\n",
    "            if steps <= k:\n",
    "                cur += 1\n",
    "                k -= steps\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n, k) -> int:\n",
    "        cur = 1\n",
    "        prefix = 1\n",
    "\n",
    "        while cur <k:\n",
    "            cnt = self.get_count(prefix,n)\n",
    "            if cur + cnt >k:\n",
    "                prefix *= 10\n",
    "                cur += 1\n",
    "            else:\n",
    "                prefix += 1\n",
    "                cur += cnt\n",
    "        return prefix\n",
    "\n",
    "    def get_count(self, i, n):\n",
    "\n",
    "        if i <= n:\n",
    "            cnt = 1\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "        a = i\n",
    "        b = i + 1\n",
    "\n",
    "        while True:\n",
    "            a = a * 10\n",
    "            b = b * 10\n",
    "            if n >= b:\n",
    "                cnt += b - a\n",
    "            elif n >= a:\n",
    "                cnt += n - a + 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        n_str = str(n)\n",
    "        n_len = len(n_str)\n",
    "\n",
    "        # Return digit beginning\n",
    "        # If bit is 1st, the digit is 1~9\n",
    "        # If bit is subsequeent,  the digit is 0~9\n",
    "        def count(digit:int, prefix: str):\n",
    "            ret = 0\n",
    "            new_pre = prefix + str(digit)\n",
    "            if new_pre < n_str[0:len(new_pre)]:\n",
    "                ret = 1\n",
    "                for i in range(1, n_len-len(prefix)):\n",
    "                    ret += 10 ** i\n",
    "            elif new_pre == n_str[0:len(new_pre)]:\n",
    "                ret = 1\n",
    "                for i in range(1, n_len-len(prefix)-1):\n",
    "                    ret += 10 ** i\n",
    "                if len(n_str) > len(new_pre):ret += 1 + int(n_str[len(new_pre):])\n",
    "            else:\n",
    "                for i in range(0, n_len-len(prefix)-1):\n",
    "                    ret += 10 ** i\n",
    "            return ret\n",
    "        \n",
    "        prefix = ''\n",
    "        cnt = k\n",
    "        while cnt:\n",
    "            cur_cnt, pre_cnt = 0, 0\n",
    "            for i in range(10):\n",
    "                if prefix == '' and i == 0:\n",
    "                    continue\n",
    "                pre_cnt = cur_cnt\n",
    "                cur_cnt += count(i, prefix)\n",
    "                if cur_cnt >= cnt:break\n",
    "            if cur_cnt == cnt:\n",
    "                prefix += str(i)\n",
    "                if prefix < n_str[0:len(prefix)]:\n",
    "                    prefix = prefix.ljust(n_len, '9')\n",
    "                elif prefix == n_str[0:len(prefix)]:\n",
    "                    prefix = n_str\n",
    "                else:\n",
    "                    prefix = prefix.ljust(n_len-1, '9')\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt -= pre_cnt\n",
    "                prefix += str(i)\n",
    "                cnt -= 1\n",
    "        \n",
    "        return int(prefix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(bd, m):\n",
    "            a, b = str(m), str(bd)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum([10**i for i in range(k)]) if k else 0\n",
    "\n",
    "            u = int(b[:len(a)])\n",
    "            if u > m: ans += 10**k \n",
    "            elif u == m: ans += bd - m * 10**k + 1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(n, pref)\n",
    "            if k <= cnt: pref, k = pref * 10, k - 1\n",
    "            else: pref, k = pref + 1, k - cnt\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def getchild(now):\n",
    "            first=now*10\n",
    "            last=now*10+9\n",
    "            num=1\n",
    "            while last<n:\n",
    "                num+=last-first+1\n",
    "                first=first*10\n",
    "                last=last*10+9\n",
    "            if n>=first:\n",
    "                num+=n-first+1\n",
    "            return num\n",
    "        # \n",
    "        def find(now,k):\n",
    "            # print(now,k)\n",
    "            if k==1:\n",
    "                return now\n",
    "            now_child=getchild(now)\n",
    "            # print('a',now_child)\n",
    "            if now_child<k:\n",
    "                return find(now+1,k-now_child)\n",
    "            else:\n",
    "                return find(now*10,k-1)\n",
    "                # first=now*10\n",
    "                # last=min(now*10+9,n)\n",
    "                # if k<=last-first+2:\n",
    "                #     return first+k-2\n",
    "                \n",
    "                # return find(now)\n",
    "        return find(1,k)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getSteps(self, cur, n):\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def count_num_tree(cur, n):  #计算当前节点cur对应10叉树的结点总数\n",
    "            count, first, last = 0, cur, cur\n",
    "            while first <= n:  #逐层遍历\n",
    "                count += (min(last, n) - first + 1)\n",
    "                first = 10*first\n",
    "                last = last = last * 10 + 9\n",
    "            return count\n",
    "\n",
    "\n",
    "        cur = 1  # 当前节点\n",
    "        k -= 1  # 遍历当前节点\n",
    "        while k:\n",
    "            count = count_num_tree(cur, n)  # 获取当前节点所在树的节点数量\n",
    "            if count <= k:  # 如果节点数小于k，则遍历右边的树\n",
    "                cur += 1\n",
    "                k -= count\n",
    "            else:           # 否则对子树遍历\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def getSteps(cur):\n",
    "            steps, first, last = 0, cur, cur\n",
    "            while first <= n:\n",
    "                steps += min(last, n) - first + 1\n",
    "                first *= 10\n",
    "                last = last * 10 + 9\n",
    "            return steps\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = getSteps(cur)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def getsteps(cur,n):\n",
    "            step,first,last = 0,cur,cur\n",
    "            while first<=n:\n",
    "                step += min(n,last)-first + 1\n",
    "                first *= 10 #### 下一层的最左边\n",
    "                last = last*10+9 ####下一层的最右边\n",
    "            return step\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k :\n",
    "            step = getsteps(cur,n)\n",
    "            if step <= k:\n",
    "                cur += 1\n",
    "                k -= step\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(m, limit):\n",
    "            a, b = str(m), str(limit)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum([10**i for i in range(k)]) if k else 0\n",
    "\n",
    "            u = int(b[:len(a)])\n",
    "            if u > m: ans += 10**k \n",
    "            elif u == m: ans += limit - m * 10**k + 1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(pref, n)\n",
    "            if k <= cnt: pref, k = pref * 10, k - 1\n",
    "            else: pref, k = pref + 1, k - cnt\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        \n",
    "        narr = list(str(n))\n",
    "        layer_cnts = [0, 0, 10, 110, 1110, 11110, 111110, 1111110, 11111110, 111111110]\n",
    "        base10 = int(math.log10(n))\n",
    "        cnt = 0\n",
    "        rst = []\n",
    "        remain_n = n\n",
    "        for j in range(len(narr)):\n",
    "            \n",
    "            real_preffix = int(''.join(narr[:j + 1]))\n",
    "\n",
    "            start = 1 if j == 0 else 0\n",
    "            for i in range(start, 10):\n",
    "                cur_preffix = int(''.join((str(x) for x in rst[:j])) + str(i))\n",
    "                cnt += 1 # is empty ?\n",
    "                if cnt == k:\n",
    "                    rst.append(i)\n",
    "                    return int(''.join(str(x) for x in rst))\n",
    "\n",
    "                if cur_preffix < real_preffix:\n",
    "                    tmp_base = layer_cnts[len(narr) - j]\n",
    "                elif cur_preffix == real_preffix:\n",
    "                    tmp_base = layer_cnts[len(narr) - j - 1] + remain_n - i * 10 ** (base10 - j) + 1\n",
    "                else:\n",
    "                    tmp_base = layer_cnts[len(narr) - j - 1]\n",
    "\n",
    "                if cnt + tmp_base >= k:\n",
    "                    rst.append(i)\n",
    "                    break\n",
    "                cnt += tmp_base\n",
    "            remain_n = n - cur_preffix * 10 ** (base10 - j)\n",
    "        return int(''.join(str(x) for x in rst))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(bd, m):\n",
    "            a, b = str(bd), str(m)\n",
    "            d = len(a) - len(b)\n",
    "            ans = sum([10**i for i in range(d)]) if d else 0\n",
    "\n",
    "            u = int(a[:len(b)])\n",
    "            if u > m: ans += 10**d \n",
    "            elif u == m: ans += bd-u*10**d+1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(n, pref)\n",
    "            if k <= cnt: pref, k = pref * 10, k - 1\n",
    "            else: pref, k = pref + 1, k - cnt\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def calc_step(num):\n",
    "            step = 0\n",
    "            nnum = num+1\n",
    "            while num<=n:\n",
    "                step += min(nnum, n+1)-num\n",
    "                num *= 10\n",
    "                nnum *= 10\n",
    "\n",
    "            return step\n",
    "\n",
    "        num = 1\n",
    "        k -= 1\n",
    "        while k>0:\n",
    "            step = calc_step(num)\n",
    "            if step<=k:\n",
    "                k -= step\n",
    "                num += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                num *= 10\n",
    "\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        res = 1\n",
    "        while k > 0:\n",
    "            cnt = 0\n",
    "            interval = [res, res + 1]\n",
    "            while n >= interval[0]:\n",
    "                cnt += (min(n+1, interval[1]) - interval[0])\n",
    "                interval[0] *= 10\n",
    "                interval[1] *= 10\n",
    "            if k >= cnt:\n",
    "                res += 1\n",
    "                k -= cnt\n",
    "            else:\n",
    "                k -= 1\n",
    "                res *= 10\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def cal_steps(n, n1, n2):\n",
    "            step = 0\n",
    "            while n1 <= n:\n",
    "                step += min(n2, n + 1) - n1\n",
    "                n1 *= 10\n",
    "                n2 *= 10\n",
    "            print(step)\n",
    "            return step\n",
    "        \n",
    "        cur = 1\n",
    "        k -= 1\n",
    "\n",
    "        while k > 0:\n",
    "            steps = cal_steps(n, cur, cur + 1)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                cur *= 10\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(m, mx):\n",
    "            a, b = str(m), str(mx)\n",
    "            k = len(b) - len(a)\n",
    "            ans = sum([10**i for i in range(k)]) if k else 0\n",
    "            u = int(b[:len(a)])\n",
    "            if u > m: ans += 10**k \n",
    "            elif u == m: ans += mx - u*10**k + 1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(pref, n)\n",
    "            if cnt < k: pref, k = pref + 1, k - cnt\n",
    "            else: pref, k = pref * 10, k - 1\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first *= 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def getStep(cur):\n",
    "            left = cur\n",
    "            right = cur\n",
    "            step = 0\n",
    "            while left <= n:\n",
    "                step += min(n, right) - left + 1\n",
    "                left = left * 10\n",
    "                right = right * 10 + 9\n",
    "            return step\n",
    "\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            step = getStep(cur)\n",
    "            if step <= k:\n",
    "                k -= step\n",
    "                cur += 1\n",
    "            else:\n",
    "                cur = cur * 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k > 0:\n",
    "            left = cur\n",
    "            right = cur + 1\n",
    "            node_num = 0\n",
    "            while left <= n:\n",
    "                node_num += min(right, (n+1)) - left\n",
    "                left = left * 10\n",
    "                right = right * 10\n",
    "            # print(cur, node_num)\n",
    "            # node_num -= 1\n",
    "            if node_num -1 < k:\n",
    "                k = k - node_num\n",
    "                cur = cur + 1\n",
    "            else:\n",
    "                cur = cur * 10\n",
    "                k -= 1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(x, limit):\n",
    "            a, b= str(x), str(limit)\n",
    "            k= len(b)- len(a)\n",
    "            ans= sum(10** i for i in range(k))if k else 0\n",
    "            ans += 10** k if (u:= int(b[:len(a)])) > x else limit - x*10**k + 1 if u== x else 0\n",
    "            return ans\n",
    "\n",
    "        ans = 1\n",
    "        while k > 1:\n",
    "            ans= ans +1 if (cnt:= get_cnt(ans, n)) < k else ans*10\n",
    "            k -= cnt if cnt< k else 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "\n",
    "        def getCnt(prefix, n):\n",
    "\n",
    "            cnt, cur_p, next_p = 0, prefix, prefix + 1\n",
    "            while cur_p <= n:\n",
    "                cnt += min(next_p, n + 1) - cur_p\n",
    "                cur_p *= 10\n",
    "                next_p *= 10\n",
    "            \n",
    "            return cnt\n",
    "        \n",
    "        cur_cnt, prefix = 1, 1\n",
    "        while cur_cnt < k:\n",
    "            cnt = getCnt(prefix, n)\n",
    "            if cur_cnt + cnt > k:\n",
    "                prefix *= 10\n",
    "                cur_cnt += 1\n",
    "            else:\n",
    "                prefix += 1\n",
    "                cur_cnt += cnt\n",
    "        \n",
    "        return prefix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSteps(self, cur: int, n: int) -> int:\n",
    "        steps, first, last = 0, cur, cur\n",
    "        while first <= n:\n",
    "            steps += min(last, n) - first + 1\n",
    "            first = first * 10\n",
    "            last = last * 10 + 9\n",
    "        return steps\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = self.getSteps(cur, n)\n",
    "            if steps <= k: # 层序遍历\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else: # 深度遍历\n",
    "                k -= 1 \n",
    "                cur *= 10\n",
    "        return cur\n",
    "\n",
    "\n",
    "\n",
    "    # def getSteps(self, cur: int, n: int) -> int:\n",
    "    #     steps, first, last = 0, cur, cur\n",
    "    #     while first <= n:\n",
    "    #         steps += min(last, n) - first + 1\n",
    "    #         first *= 10 \n",
    "    #         last = last * 10 + 9\n",
    "    #     return steps\n",
    "    # def findKthNumber(self, n: int, k: int) -> int:\n",
    "    #     cur = 1\n",
    "    #     k -= 1\n",
    "    #     while k:\n",
    "    #         steps = self.getSteps(cur, n)\n",
    "    #         if steps <= k:\n",
    "    #             k -= steps\n",
    "    #             cur += 1\n",
    "    #         else:\n",
    "    #             cur *= 10\n",
    "    #             k -= 1\n",
    "    #     return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getSubTreeNode(self, n, v):\n",
    "        num = 0\n",
    "        cur = v\n",
    "        next = v + 1\n",
    "\n",
    "        while cur <= n:\n",
    "            num += min(next, n+1) - cur\n",
    "            cur *= 10\n",
    "            next *= 10\n",
    "        return num\n",
    "\n",
    "\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        v = 1\n",
    "        k -= 1\n",
    "        while k>0:\n",
    "            num = self.getSubTreeNode(n, v)\n",
    "            if num<=k:\n",
    "                v += 1\n",
    "                k -= num\n",
    "            else:\n",
    "                v *= 10\n",
    "                k -= 1\n",
    "        return v\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def count_num_tree(cur, n):  #计算当前节点cur对应10叉树的结点总数\n",
    "            count, first, last = 0, cur, cur #first 和 last表示每一层的第一个节点和最后一个节点\n",
    "            while first <= n:  #逐层遍历\n",
    "                count += (min(last, n) - first + 1)\n",
    "                first = 10*first\n",
    "                last = last * 10 + 9\n",
    "            return count\n",
    "\n",
    "\n",
    "        cur = 1  # 当前节点\n",
    "        k -= 1  # 遍历当前节点\n",
    "        while k:\n",
    "            count = count_num_tree(cur, n)  # 获取当前节点所在树的节点数量\n",
    "            if count <= k:  # 如果节点数小于k，则遍历右边的树\n",
    "                cur += 1\n",
    "                k -= count\n",
    "            else:           # 否则对子树遍历\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n",
    "\n",
    "#https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1363067/zhi-xing-yong-shi-cong-5-by-kind-curiehx-fdio/\n",
    "\n",
    "#与 第386题 配合理解 效果更佳"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_steps(cur, n):\n",
    "            first, last = cur, cur\n",
    "            steps = 0\n",
    "            while first <= n:\n",
    "                steps += min(last, n) - first + 1\n",
    "                first *= 10\n",
    "                last = last * 10 + 9\n",
    "            return steps\n",
    "\n",
    "        \n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = get_steps(cur, n)\n",
    "            if steps <= k:\n",
    "                k -= steps\n",
    "                cur += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                cur *= 10\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def getStep(a):\n",
    "            b = a + 1\n",
    "            ret = 0\n",
    "            while a <= n:\n",
    "                ret += min(n + 1, b) - a\n",
    "                a *= 10\n",
    "                b *= 10\n",
    "            return ret\n",
    "        k -= 1\n",
    "        curr = 1\n",
    "        while k > 0:\n",
    "            step = getStep(curr)\n",
    "            if k - step >= 0:\n",
    "                k -= step\n",
    "                curr += 1\n",
    "            else:\n",
    "                curr *= 10\n",
    "                k -= 1\n",
    "        return curr\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_steps(cur, n):\n",
    "            first, last = cur, cur\n",
    "            steps = 0\n",
    "            while first <= n:\n",
    "                steps += min(last, n) - first + 1\n",
    "                first *= 10\n",
    "                last = 10 * last + 9\n",
    "            return steps\n",
    "\n",
    "\n",
    "\n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            steps = get_steps(cur, n)\n",
    "            if steps <= k:\n",
    "                cur += 1\n",
    "                k -= steps\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k -= 1\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def count_num(cur, n):\n",
    "            count, first, last = 0, cur, cur\n",
    "            while first <= n:\n",
    "                count += min(last,n)-first+1\n",
    "                first *= 10\n",
    "                last = last*10+9\n",
    "            return count\n",
    "\n",
    "        cur = 1\n",
    "        k-=1\n",
    "        while k:\n",
    "            count = count_num(cur,n)\n",
    "            if count <= k:\n",
    "                cur += 1\n",
    "                k-= count\n",
    "            else:\n",
    "                cur *= 10\n",
    "                k-=1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def count_num_tree(cur, n):  #计算当前节点cur对应10叉树的结点总数\n",
    "            count, first, last = 0, cur, cur\n",
    "            while first <= n:\n",
    "                count += (min(last,n)-first+1)\n",
    "                first = first*10\n",
    "                last = last*10 + 9\n",
    "            return count\n",
    "        \n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            count = count_num_tree(cur, n)\n",
    "            if count <= k:\n",
    "                cur += 1\n",
    "                k -= count\n",
    "            else:\n",
    "                cur = cur*10\n",
    "                k -= 1\n",
    "        return cur\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(bd, m):\n",
    "            a, b = str(bd), str(m)\n",
    "            d = len(a)-len(b)\n",
    "            ans = sum([10**i for i in range(d)]) if d else 0\n",
    "\n",
    "            u = int(a[:len(b)])\n",
    "            if u > m: ans += 10**d \n",
    "            elif u == m: ans += bd-u*10**d+1\n",
    "            return ans\n",
    "\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(n, pref)\n",
    "            if k <= cnt: pref, k = pref * 10, k - 1\n",
    "            else: pref, k = pref + 1, k - cnt\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        pre = 1\n",
    "        cnt = 0\n",
    "        def getpre(prefix):\n",
    "            cur = prefix\n",
    "            next = prefix+1\n",
    "            count = 0\n",
    "            while cur<=n:\n",
    "                count += min(next-cur, n-cur+1)\n",
    "                cur *= 10\n",
    "                next *= 10\n",
    "            return count \n",
    "        while k>1:\n",
    "            cnt = getpre(pre)   \n",
    "            if cnt<k:\n",
    "                pre += 1\n",
    "                k -= cnt     \n",
    "            else:\n",
    "                pre *= 10\n",
    "                k -= 1\n",
    "        return pre  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        cnt = 0\n",
    "        res = 1\n",
    "        def getCount(res:int, n:int) -> int:\n",
    "            tcnt = 0\n",
    "            width = 1\n",
    "            while True:\n",
    "                if res + width - 1 <= n:\n",
    "                    tcnt += width\n",
    "                    res *= 10\n",
    "                    width *= 10\n",
    "                else:\n",
    "                    if n - res >= 0:\n",
    "                        tcnt += n - res + 1\n",
    "                    break\n",
    "            return tcnt\n",
    "\n",
    "        while True:\n",
    "            if cnt == k-1:\n",
    "                break\n",
    "            tmp = getCount(res, n)\n",
    "            if cnt + tmp >= k:\n",
    "                res *= 10\n",
    "                cnt += 1\n",
    "            else:\n",
    "                res += 1\n",
    "                cnt += tmp\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def search(pos, n, max_node):\n",
    "    if pos > n:\n",
    "        return 0\n",
    "    level_count = min(max_node - pos + 1, n - pos + 1)\n",
    "    max_node = max_node * 10 + 9\n",
    "    return level_count + search(pos * 10, n, max_node)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        pos = 1\n",
    "        k-=1\n",
    "        while k > 0:\n",
    "            count = search(pos, n, pos)\n",
    "            if count <= k:\n",
    "                k -= count\n",
    "                pos += 1\n",
    "            else:\n",
    "                pos *= 10\n",
    "                k -= 1\n",
    "        return pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        node = 1 # 初始化节点\n",
    "        k -= 1\n",
    "        def getChildCnt(node, n):\n",
    "            cnt = 0\n",
    "            left, right = node, node + 1\n",
    "            while left <= n:\n",
    "                cnt += min(right, n + 1) - left\n",
    "                left *= 10 # 下一层左侧\n",
    "                right *= 10 # 下一层右侧\n",
    "            return cnt\n",
    "        while k:\n",
    "            childCnt = getChildCnt(node, n)\n",
    "            if childCnt > k: # 在当前节点下\n",
    "                k -= 1 # 减去当前节点数量\n",
    "                node *= 10 # 遍历下一个节点\n",
    "            else:\n",
    "                k -= childCnt\n",
    "                node += 1 # 往右侧搜索\n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        # def getCnt(prefix, n) -> int:\n",
    "        #     n_prefix, nn = len(str(prefix)), len(str(n))\n",
    "        #     deln = nn - n_prefix\n",
    "        #     count = 0\n",
    "        #     for i in range(deln):\n",
    "        #         count += 10**i\n",
    "            \n",
    "        #     if prefix < int(str(n)[:n_prefix]):\n",
    "        #         count += 10**deln \n",
    "        #     else:\n",
    "        #         # count += n % (10**deln) + 1 #!!!!xxxx 100 10 cannot pass!!!\n",
    "        #         count += n - prefix*(10**deln) + 1      \n",
    "        #     return count\n",
    "        def getCnt(x:int, lim:int) -> int:\n",
    "            cnt = 0\n",
    "            xstr, limstr = str(x), str(lim)\n",
    "            nx, nlim = len(xstr), len(limstr)\n",
    "            deln = nlim - nx\n",
    "            for i in range(deln):\n",
    "                cnt += 10**i \n",
    "\n",
    "            limprefix = int(limstr[:nx])\n",
    "            if limprefix > x: \n",
    "                cnt += 10**deln\n",
    "            elif limprefix == x:\n",
    "                cnt += lim - x*(10**deln) + 1 \n",
    "\n",
    "            return cnt\n",
    "        res = 1\n",
    "        while k > 1:\n",
    "            cnt = getCnt(res, n)\n",
    "            if cnt < k:\n",
    "                res += 1\n",
    "                k -= cnt\n",
    "            else:\n",
    "                res *= 10\n",
    "                k -= 1\n",
    "        return res\n",
    "\n",
    "# 49 / 69 个通过的测试用例\n",
    "##\n",
    "# [1,13] 2\n",
    "\n",
    "#  1       13   \n",
    "# /\n",
    "# 10, 11, 12, 13  => 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def get_cnt(bd, m):\n",
    "            a, b = str(bd), str(m)\n",
    "            d = len(a) - len(b)\n",
    "            ans = sum([10**i for i in range(d)]) if d else 0\n",
    "\n",
    "            u = int(a[:len(b)])\n",
    "            if u > m: ans += 10**d \n",
    "            elif u == m: ans += bd-u*10**d+1\n",
    "            return ans\n",
    "\n",
    "        pref = 1\n",
    "        while k > 1:\n",
    "            cnt = get_cnt(n, pref)\n",
    "            if k <= cnt: pref, k = pref * 10, k - 1\n",
    "            else: pref, k = pref + 1, k - cnt\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        \n",
    "\n",
    "        def getCount(prefix, limit):\n",
    "            nextPrefix = prefix + 1\n",
    "            count = 0\n",
    "            while prefix <= limit:\n",
    "                count += min(nextPrefix - prefix, limit - prefix + 1)\n",
    "                prefix *= 10\n",
    "                nextPrefix *= 10\n",
    "            return count\n",
    "\n",
    "   \n",
    "        prefix = 1\n",
    "        p = 1\n",
    "        while p < k:\n",
    "            count = getCount(prefix, n)\n",
    "            if count + p <= k:\n",
    "                prefix = prefix + 1\n",
    "                p += count\n",
    "            else:\n",
    "                prefix = prefix * 10\n",
    "                p += 1\n",
    "        return prefix\n",
    "\n",
    "        \n",
    "        \n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        k -= 1\n",
    "        res = 1\n",
    "        while k > 0:\n",
    "            cnt = 0\n",
    "            interval = [res, res + 1]\n",
    "            while n >= interval[0]:\n",
    "                cnt += (min(n + 1, interval[1]) - interval[0])\n",
    "                interval[0] *= 10\n",
    "                interval[1] *= 10\n",
    "            if cnt > k:\n",
    "                res *= 10\n",
    "                k -= 1\n",
    "            else:\n",
    "                k -= cnt\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # very slow\n",
    "    # def findKthNumber(self, n: int, k: int) -> int:\n",
    "    #     s_list = []\n",
    "    #     for i in range(1, n+1):\n",
    "    #         s_list.append(str(i))\n",
    "    #     s_list.sort()\n",
    "\n",
    "    #     return int(s_list[k-1])\n",
    "\n",
    "    # https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/1360676/pythonjavajavascriptgo-di-gui-by-himymbe-5mq5/\n",
    "    def findKthNumber(self, n: int, k: int) -> int:\n",
    "        def dfs(l, r):\n",
    "            return 0 if l > n else min(n, r) - l + 1 + dfs(l * 10, r * 10 + 9)\n",
    "        \n",
    "        cur = 1\n",
    "        k -= 1\n",
    "        while k:\n",
    "            cnts = dfs(cur, cur)\n",
    "            if cnts <= k:\n",
    "                k -= cnts\n",
    "                cur += 1\n",
    "            else:\n",
    "                k -= 1\n",
    "                cur *= 10\n",
    "        \n",
    "        return cur"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
